package com.example.leetcode.c601_c700.c647;
/**
 * 给定一个非空二叉树, 返回一个由每层节点平均值组成的数组。
 *
 *  
 *
 * 示例 1：
 *
 * 输入：
 *     3
 *    / \
 *   9  20
 *     /  \
 *    15   7
 * 输出：[3, 14.5, 11]
 * 解释：
 * 第 0 层的平均值是 3 ,  第1层是 14.5 , 第2层是 11 。因此返回 [3, 14.5, 11] 。
 *  
 *
 * 提示：
 *
 * 节点值的范围在32位有符号整数范围内。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/average-of-levels-in-binary-tree
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */


import com.example.leetcode.common.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * 二叉树的层平均值
 *
 * @author zhanpengguo
 * @date 2020-09-12 10:00
 */
public class Solution {


    private List<Double> sums = new ArrayList<>();
    private List<Integer> counts = new ArrayList<>();

    public List<Double> averageOfLevels(TreeNode root) {
        bianli(root, 0);
        for (int i = 1; i < sums.size(); i++) {
            sums.set(i, sums.get(i) / counts.get(i));
        }
        return sums;
    }

    private void bianli(TreeNode root, int cur) {
        if (root == null) {
            return;
        }
        // cur表示当前层数-1
        if (sums.size() - 1 < cur) {
            sums.add((double) root.val);
            counts.add(1);
        } else {
            sums.set(cur, sums.get(cur) + root.val);
            counts.set(cur, counts.get(cur) + 1);
        }
        bianli(root.left, cur + 1);
        bianli(root.right, cur + 1);
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        TreeNode root = new TreeNode(3);

        TreeNode left = new TreeNode(Integer.MAX_VALUE);
        left.left = new TreeNode(10);
        root.left = left;

        TreeNode right = new TreeNode(Integer.MAX_VALUE);
        right.left = new TreeNode(15);
        right.right = new TreeNode(7);
        root.right = right;
        List<Double> list = solution.averageOfLevels(root);
//        list.add(3.0);
//        list.add(2.0);
//        list.set(1, 4.0);
        System.out.println(list);
        System.out.println("============");
        System.out.println(solution.counts);
    }

    public List<Double> averageOfLevels1(TreeNode root) {
        List<Integer> counts = new ArrayList<Integer>();
        List<Double> sums = new ArrayList<Double>();
        dfs(root, 0, counts, sums);
        List<Double> averages = new ArrayList<Double>();
        int size = sums.size();
        for (int i = 0; i < size; i++) {
            averages.add(sums.get(i) / counts.get(i));
        }
        return averages;
    }

    public void dfs(TreeNode root, int level, List<Integer> counts, List<Double> sums) {
        if (root == null) {
            return;
        }
        if (level < sums.size()) {
            sums.set(level, sums.get(level) + root.val);
            counts.set(level, counts.get(level) + 1);
        } else {
            sums.add(1.0 * root.val);
            counts.add(1);
        }
        dfs(root.left, level + 1, counts, sums);
        dfs(root.right, level + 1, counts, sums);
    }

}
